package com.zzz.dynamic;

import java.util.Arrays;




/**
 *
 * 最长递增公共子序列
 *
 * 第一步：将问题试着拆分成子问题
 * 求解 m个字符的s1  和 n个字符 的s2  的 公共子序列：
 * 当 s1[m] == s2[n]   那么  s1和s2的公共子序列长度为   s1[1 - (n-1)] 与 s2[1 - (m-1)] + 1
 * 如果 不等于           那么                         s1[1-(n-1)] 与 s2[1-m] 的长度     和   s1[1-n] 与 s2[1-(m-1)] 长度  中大的那个
 *
 * 问题的本质：
 * 有 s1,s2 连个字符串   数字i:表示 s1字符位置  j:表示s2字符位置   i范围[0,s1.length]  j范围[0,s2.length]
 *          |-    0                        i==0  or  j==0
 * l(i,j) = |    l(i-1,j-1) + 1            s1[i-1] == s2[j-1]
 *          |-   max(l(i,j-1), l(i-1,j))   s1[i-1] != s2[j-1]
 * @author zizan
 */

public class LongCommonSequence {
    public static void main(String[] args) {

        String s1 = "ABCBDAB";
        String s2 = "BDCABA";

//        String s1 = "BD";
//        String s2 = "AB";

        elementsLen = new int[s1.length()][s2.length()];

        lcsFromDown1(s1.toCharArray(), s2.toCharArray());

        for (int[] ints : elementsLen) {
            System.out.println(Arrays.toString(ints));
        }

        System.out.println("----------------------------------");

        System.out.println(elementsLen[s1.length() - 1][s2.length() - 1]);
    }

    /*
     *  动态规划的思想就是使用空间换时间，把最长公共子序列的问题转化成子问题求解之后
     *  需要额外的空间存储子问题的结果，以用来后续计算的时候直接使用
     *
     * 本例中，需要使用 一个两维数组，空间为 int[s2.length()][s1.length]  用来存储 c[i][j] 的 最长递增子序列的值
     * 因为 共有 i * j 种子问题
     *
     *
     *
     */

    public static int[][] elementsLen;

    public static void lcsFromUp(char[] chars1, char[] chars2) {

        for (int[] ints : elementsLen) {
            Arrays.fill(ints, -1);
        }

        for (int i = chars1.length; i > 0; i--) {
            for (int j = chars2.length; j > 0; j--) {
                //System.out.print("c[" + i + "][" + j + "] ");
                if (i == chars1.length && j == 1) {
                    int x = 1;
                }
                lcsFromUp(chars1, chars2, i, j);
            }
            //System.out.println();
        }
    }


    public static int lcsFromUp(char[] chars1, char[] chars2, int i, int j) {
        if (i <= 0 || j <= 0) {
            return 0;
        }

        if (elementsLen[i - 1][j - 1] >= 0) {
            return elementsLen[i - 1][j - 1];
        }

        if (chars1[i - 1] == chars2[j - 1]) {
            elementsLen[i - 1][j - 1] = lcsFromUp(chars1, chars2, i - 1, j - 1) + 1;
        } else {
            elementsLen[i - 1][j - 1] = Math.max(lcsFromUp(chars1, chars2, i, j - 1), lcsFromUp(chars1, chars2, i - 1, j));
        }

        return elementsLen[i - 1][j - 1];
    }


    /*
        自底向上求解
        因为 需要判断 边界 i = 1  和  边界  j = 1的情况 而又不能像递归那样 如果边界小于1就直接返回0
        所以 每次字符比较 都需要处理 i==j && j==1   |   i == 1    |    j==1   |   i>1 && j>1   四种情况

        但是如果增大存储使用空间，就无需这么判断 为何且看下一个
     */
    public static void lcsFromDown(char[] chars1, char[] chars2) {
        for (int i = 1; i <= chars1.length; i++) {
            for (int j = 1; j <= chars2.length; j++) {


                if (chars1[i - 1] == chars2[j - 1]) {
                    if (i == 1 || j == 1) {
                        if (i == 1 && j == 1)
                            elementsLen[i - 1][j - 1] = 1;
                        else if (i == 1) {
                            elementsLen[i - 1][j - 1] = elementsLen[i - 1][j - 2] + 1;
                        } else {
                            elementsLen[i - 1][j - 1] = elementsLen[i - 2][j - 1] + 1;
                        }

                    } else {
                        elementsLen[i - 1][j - 1] = elementsLen[i - 2][j - 2] + 1;
                    }
                } else {
                    if (i == 1 || j == 1) {
                        if (i == 1 && j == 1)
                            elementsLen[i - 1][j - 1] = 0;
                        else if (i == 1) {
                            elementsLen[i - 1][j - 1] = elementsLen[i - 1][j - 2];
                        } else {
                            elementsLen[i - 1][j - 1] = elementsLen[i - 2][j - 1];
                        }

                    } else {
                        elementsLen[i - 1][j - 1] = Math.max(elementsLen[i - 2][j - 1], elementsLen[i - 1][j - 2]);
                    }
                }


            }
        }
    }


    /*
        算法导论上的 自底向上求解  使用的辅助空间和我不一样，所以代码更简洁，不需要这么多判断
        使用辅助空间 elementsLen[s1.length() + 1][s2.length()+1]
     */
    public static void lcsFromDown1(char[] chars1, char[] chars2) {

        elementsLen = new int[chars1.length + 1][chars2.length + 1];

        for (int i = 1; i <= chars1.length; i++) {
            for (int j = 1; j <= chars2.length; j++) {

                if (chars1[i - 1] == chars2[j - 1]) {
                    elementsLen[i][j] = elementsLen[i - 1][j - 1] + 1;
                } else {
                    elementsLen[i][j] = Math.max(elementsLen[i - 1][j], elementsLen[i][j - 1]);
                }

            }
        }
    }

}
